package top.minuy.structure.graph.search.breadth;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 广度优先遍历
 *
 * @author Minuy
 * @time 22:29
 * @date 2021/11/19
 */
public class GraphBFS {

    private Graph g;
    private boolean[] isVisited;

    private List<Integer> order;

    public GraphBFS(Graph g) {
        this.g = g;

        isVisited = new boolean[g.V()];

        order = new ArrayList<>();

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                bfs(v);
                // System.out.println("根顶点："+v);
            }
        }
    }

    private void bfs(int v) {
        List<Integer> queue = new ArrayList<>();
        queue.add(v); // 根顶点入队
        isVisited[v] = true; // 入队的时候设置为true
        // System.out.println("根顶点入队："+v);
        // System.out.println("==============");
        while (!queue.isEmpty()) {
            // 第一个元素出队
            v = queue.remove(0);
            // System.out.println("第一个元素出队并访问："+v);

            // 访问
            order.add(v);

            for (int w : g.adj(v)) {
                if (!isVisited[w]) {  // 如果没被访问过
                    queue.add(w);  // 入队
                    // System.out.println("子顶点入队："+w);
                    isVisited[w] = true; // 入队的时候设置为true
                }
            }
        }
    }

    public Iterable<Integer> order(){
        return order;
    }

}
